package com.yun.algorithmproblem.leetcode;

public class Leetcode729 {
    static class MyCalendar {
        public MyCalendar() {

        }

        public boolean book(int start, int end) {
            if (query(root, 0, N, start, end-1) == 0) {
                update(root, 0, N, start, end-1, 1);
                return true;
            }
            return false;
        }

        /**
         * 线段树模板
         */
        class Node {
            Node left, right;
            int val, add;
        }

        private final int N = (int) 1e9;
        private Node root = new Node();

        public void update(Node node, int start, int end, int l, int r, int val) {
            //当前区间在添加区间内
            if (l <= start && end <= r) {
                node.val += val;
                node.add += val;
                return;
            }
            int mid = (start + end) >> 1;
            pushDown(node);
            //更新左右的节点
            if (l <= mid) {
                update(node.left, start, mid, l, r, val);
            }
            if (r > mid) {
                update(node.right, mid + 1, end, l, r, val);
            }
            //更新当前区间的值
            pushUp(node);
        }

        public int query(Node node, int start, int end, int l, int r) {
            //当前区间在查询区间内
            if (l <= start && end <= r) {
                return node.val;
            }
            int mid = (start + end) >> 1, ans = 0;
            pushDown(node);
            if (l <= mid) {
                ans = query(node.left, start, mid, l, r);
            }
            if (r > mid) {
                ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
            }
            return ans;
        }

        private void pushUp(Node node) {
            node.val = Math.max(node.left.val, node.right.val);
        }

        private void pushDown(Node node) {
            if (node.left == null) {
                node.left = new Node();
            }
            if (node.right == null) {
                node.right = new Node();
            }
            if (node.add == 0) {
                return;
            }
            node.left.val = node.val;
            node.right.val = node.val;
            node.left.add = node.add;
            node.right.add = node.add;
            node.add = 0;
        }
    }


    public static void main(String[] args) {
        MyCalendar obj = new MyCalendar();
        System.out.println(obj.book(10, 20));
        System.out.println(obj.book(15, 25));
        System.out.println(obj.book(20, 30));
    }
}
